package demo.practice.competition;

import java.util.*;

public class P5860 {

    public static void main(String[] args) {
        P5860 p5860 = new P5860();
        p5860.findOriginalArray(new int[]{2, 1, 2, 4, 2, 4});
    }

    public int[] findOriginalArray(int[] changed) {
        Arrays.sort(changed);
        //boolean[] bj = new boolean[changed.length];
        if (changed == null || changed.length == 0 || (changed.length & 1) == 1)
            return new int[0];
        //Set<Integer> set = new HashSet<>();
        Map<Integer, Integer> map = new HashMap<>();

        int[] res = new int[changed.length / 2];

        int c = 0;
        for (int i = 0; i < changed.length; i++) {
            if (map.containsKey(changed[i])) {
                if (map.get(changed[i]) - 1 > 0) {
                    map.put(changed[i], map.get(changed[i]) - 1);
                } else {
                    map.remove(changed[i]);
                }
            } else {
                if (c >= res.length)
                    return new int[0];

                if(map.containsKey(changed[i] * 2)){
                    map.put(changed[i] * 2, map.get(changed[i] * 2) + 1);
                }else {
                    map.put(changed[i] * 2, 1);
                }

                res[c++] = changed[i];
            }
        }
        return map.isEmpty() ? res : new int[0];
    }
}
